package com.linzm.leetcode.primary.栈和队列;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Stack;

/**
 * @Author zimingl
 * @Date 2022/10/7 11:45
 * @Description: TODO
 */
public class 栈和队列1047删除字符串中的所有相邻重复项 {

    public String removeDuplicates(String s) {
        if (s == null || s.trim().equals(" ")){
            return "";
        }
        Stack<Character> stack = new Stack<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            if (!stack.isEmpty() && stack.peek() == ch){
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        String resStr = "";
        while (!stack.isEmpty()){
            resStr = stack.pop()+resStr;
        }
        return resStr;
    }

    public String removeDuplicates2(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }

    @Test
    public void test(){
        String s = "abbaca";
        String removeDuplicates = removeDuplicates(s);
        System.out.println(removeDuplicates);
    }
}
